import java.util.Arrays;

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int row= mat.length;
        int col=mat[0].length;
        int[][] ret = new int[row][col];
        for(int i=0;i<row;i++) {
            for(int n=0;n<col;n++) {
                ret[i][n]=Integer.MAX_VALUE/2;
            }
        }
        for(int i=0;i<row;i++) {
            for(int n=0;n<col;n++) {
                if(mat[i][n]==0) {
                    ret[i][n]=0;
                } else {
                    if(i>0) {
                        ret[i][n]=Math.min(ret[i][n],ret[i-1][n]+1);
                    }
                    if(n>0) {
                        ret[i][n]=Math.min(ret[i][n],ret[i][n-1]+1);
                    }
                }
            }
        }
        for(int i=row-1;i>=0;i--) {
            for(int n=col-1;n>=0;n--) {
                if(mat[i][n]==0) {
                    ret[i][n]=0;
                } else {
                    if(i<row-1) {
                        ret[i][n]=Math.min(ret[i][n],ret[i+1][n]+1);
                    }
                    if(n<col-1) {
                        ret[i][n]=Math.min(ret[i][n],ret[i][n+1]+1);
                    }
                }
            }
        }
        return ret;
    }
}
public class lc542 {
}
